#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=1e5+5,mod=111121;
int n,a[Maxn];
int head[Maxn],to[Maxn<<1],nxt[Maxn<<1],cnt1;
inline void add(int u,int v){
	to[++cnt1]=v;nxt[cnt1]=head[u];
	head[u]=cnt1;
}
inline int ksm(int a,int k){
	int res=1;k%=mod-1;
	if(a==0)return 0;
	for(;k;k>>=1,a=a*a%mod)
		if(k&1)res=res*a%mod;
	return res;
}
namespace sub1{
	int f[Maxn],dep[Maxn];
	void dfs(int u,int v){
		f[u]=v;dep[u]=dep[v]+1;
		for(int i=head[u];i;i=nxt[i]){
			int y=to[i];
			if(y==v)continue;
			dfs(y,u);
		}
	}
	inline void solve(){
		int res=0;dfs(1,0);
		for(int i=1;i<=n;i++){
			for(int j=i;j<=n;j++){
				int v1=(1ll<<32)-1,v2=0;
				int u=i,v=j;
				if(dep[u]<dep[v])swap(u,v);
				while(dep[u]>dep[v])v1&=a[u],v2|=a[u],u=f[u];
				while(u!=v)v1&=a[u],v1&=a[v],v2|=a[u],v2|=a[v],u=f[u],v=f[v];
				v1&=a[u];v2|=a[u];
				res=(res+ksm(v1,v2))%mod;
//				printf("[%d,%d]={%d,%d,%d}\n",i,j,v1,v2,ksm(v1,v2));
			}
		}printf("%lld\n",res);
	}
}
signed main(){
	freopen("abstract.in","r",stdin);
	freopen("abstract.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	if(n<=50)sub1::solve();
	return 0;
}

